home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / B-C / Berkeley-yacc-mpw / mkpar.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-14  |  8.1 KB  |  396 lines  |  [TEXT/MPS ]
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Robert Paul Corbett.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. static char sccsid[] = "@(#)mkpar.c    5.3 (Berkeley) 1/20/91";
  39. #endif /* not lint */
  40.  
  41. #include "defs.h"
  42.  
  43. action **parser;
  44. int SRtotal;
  45. int RRtotal;
  46. short *SRconflicts;
  47. short *RRconflicts;
  48. short *defred;
  49. short *rules_used;
  50. short nunused;
  51. short final_state;
  52.  
  53. static int SRcount;
  54. static int RRcount;
  55.  
  56. extern action *parse_actions();
  57. extern action *get_shifts();
  58. extern action *add_reductions();
  59. extern action *add_reduce();
  60.  
  61.  
  62. make_parser()
  63. {
  64.     register int i;
  65.  
  66.     parser = NEW2(nstates, action *);
  67.     for (i = 0; i < nstates; i++)
  68.     parser[i] = parse_actions(i);
  69.  
  70.     find_final_state();
  71.     remove_conflicts();
  72.     unused_rules();
  73.     if (SRtotal + RRtotal > 0) total_conflicts();
  74.     defreds();
  75. }
  76.  
  77.  
  78. action *
  79. parse_actions(stateno)
  80. register int stateno;
  81. {
  82.     register action *actions;
  83.  
  84.     actions = get_shifts(stateno);
  85.     actions = add_reductions(stateno, actions);
  86.     return (actions);
  87. }
  88.  
  89.  
  90. action *
  91. get_shifts(stateno)
  92. int stateno;
  93. {
  94.     register action *actions, *temp;
  95.     register shifts *sp;
  96.     register short *to_state;
  97.     register int i, k;
  98.     register int symbol;
  99.  
  100.     actions = 0;
  101.     sp = shift_table[stateno];
  102.     if (sp)
  103.     {
  104.     to_state = sp->shift;
  105.     for (i = sp->nshifts - 1; i >= 0; i--)
  106.     {
  107.         k = to_state[i];
  108.         symbol = accessing_symbol[k];
  109.         if (ISTOKEN(symbol))
  110.         {
  111.         temp = NEW(action);
  112.         temp->next = actions;
  113.         temp->symbol = symbol;
  114.         temp->number = k;
  115.         temp->prec = symbol_prec[symbol];
  116.         temp->action_code = SHIFT;
  117.         temp->assoc = symbol_assoc[symbol];
  118.         actions = temp;
  119.         }
  120.     }
  121.     }
  122.     return (actions);
  123. }
  124.  
  125. action *
  126. add_reductions(stateno, actions)
  127. int stateno;
  128. register action *actions;
  129. {
  130.     register int i, j, m, n;
  131.     register int ruleno, tokensetsize;
  132.     register unsigned *rowp;
  133.  
  134.     tokensetsize = WORDSIZE(ntokens);
  135.     m = lookaheads[stateno];
  136.     n = lookaheads[stateno + 1];
  137.     for (i = m; i < n; i++)
  138.     {
  139.     ruleno = LAruleno[i];
  140.     rowp = LA + i * tokensetsize;
  141.     for (j = ntokens - 1; j >= 0; j--)
  142.     {
  143.         if (BIT(rowp, j))
  144.         actions = add_reduce(actions, ruleno, j);
  145.     }
  146.     }
  147.     return (actions);
  148. }
  149.  
  150.  
  151. action *
  152. add_reduce(actions, ruleno, symbol)
  153. register action *actions;
  154. register int ruleno, symbol;
  155. {
  156.     register action *temp, *prev, *next;
  157.  
  158.     prev = 0;
  159.     for (next = actions; next && next->symbol < symbol; next = next->next)
  160.     prev = next;
  161.  
  162.     while (next && next->symbol == symbol && next->action_code == SHIFT)
  163.     {
  164.     prev = next;
  165.     next = next->next;
  166.     }
  167.  
  168.     while (next && next->symbol == symbol &&
  169.         next->action_code == REDUCE && next->number < ruleno)
  170.     {
  171.     prev = next;
  172.     next = next->next;
  173.     }
  174.  
  175.     temp = NEW(action);
  176.     temp->next = next;
  177.     temp->symbol = symbol;
  178.     temp->number = ruleno;
  179.     temp->prec = rprec[ruleno];
  180.     temp->action_code = REDUCE;
  181.     temp->assoc = rassoc[ruleno];
  182.  
  183.     if (prev)
  184.     prev->next = temp;
  185.     else
  186.     actions = temp;
  187.  
  188.     return (actions);
  189. }
  190.  
  191.  
  192. find_final_state()
  193. {
  194.     register int goal, i;
  195.     register short *to_state;
  196.     register shifts *p;
  197.  
  198.     p = shift_table[0];
  199.     to_state = p->shift;
  200.     goal = ritem[1];
  201.     for (i = p->nshifts - 1; i >= 0; --i)
  202.     {
  203.     final_state = to_state[i];
  204.     if (accessing_symbol[final_state] == goal) break;
  205.     }
  206. }
  207.  
  208.  
  209. unused_rules()
  210. {
  211.     register int i;
  212.     register action *p;
  213.  
  214.     rules_used = (short *) MALLOC(nrules*sizeof(short));
  215.     if (rules_used == 0) no_space();
  216.  
  217.     for (i = 0; i < nrules; ++i)
  218.     rules_used[i] = 0;
  219.  
  220.     for (i = 0; i < nstates; ++i)
  221.     {
  222.     for (p = parser[i]; p; p = p->next)
  223.     {
  224.         if (p->action_code == REDUCE && p->suppressed == 0)
  225.         rules_used[p->number] = 1;
  226.     }
  227.     }
  228.  
  229.     nunused = 0;
  230.     for (i = 3; i < nrules; ++i)
  231.     if (!rules_used[i]) ++nunused;
  232.  
  233.     if (nunused)
  234.     if (nunused == 1)
  235.         fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  236.     else
  237.         fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  238. }
  239.  
  240.  
  241. remove_conflicts()
  242. {
  243.     register int i;
  244.     register int symbol;
  245.     register action *p, *pref;
  246.  
  247.     SRtotal = 0;
  248.     RRtotal = 0;
  249.     SRconflicts = NEW2(nstates, short);
  250.     RRconflicts = NEW2(nstates, short);
  251.     for (i = 0; i < nstates; i++)
  252.     {
  253.     SRcount = 0;
  254.     RRcount = 0;
  255.     symbol = -1;
  256.     for (p = parser[i]; p; p = p->next)
  257.     {
  258.         if (p->symbol != symbol)
  259.         {
  260.         pref = p;
  261.         symbol = p->symbol;
  262.         }
  263.         else if (i == final_state && symbol == 0)
  264.         {
  265.         SRcount++;
  266.         p->suppressed = 1;
  267.         }
  268.         else if (pref->action_code == SHIFT)
  269.         {
  270.         if (pref->prec > 0 && p->prec > 0)
  271.         {
  272.             if (pref->prec < p->prec)
  273.             {
  274.             pref->suppressed = 2;
  275.             pref = p;
  276.             }
  277.             else if (pref->prec > p->prec)
  278.             {
  279.             p->suppressed = 2;
  280.             }
  281.             else if (pref->assoc == LEFT)
  282.             {
  283.             pref->suppressed = 2;
  284.             pref = p;
  285.             }
  286.             else if (pref->assoc == RIGHT)
  287.             {
  288.             p->suppressed = 2;
  289.             }
  290.             else
  291.             {
  292.             pref->suppressed = 2;
  293.             p->suppressed = 2;
  294.             }
  295.         }
  296.         else
  297.         {
  298.             SRcount++;
  299.             p->suppressed = 1;
  300.         }
  301.         }
  302.         else
  303.         {
  304.         RRcount++;
  305.         p->suppressed = 1;
  306.         }
  307.     }
  308.     SRtotal += SRcount;
  309.     RRtotal += RRcount;
  310.     SRconflicts[i] = SRcount;
  311.     RRconflicts[i] = RRcount;
  312.     }
  313. }
  314.  
  315.  
  316. total_conflicts()
  317. {
  318.     fprintf(stderr, "%s: ", myname);
  319.     if (SRtotal == 1)
  320.     fprintf(stderr, "1 shift/reduce conflict");
  321.     else if (SRtotal > 1)
  322.     fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  323.  
  324.     if (SRtotal && RRtotal)
  325.     fprintf(stderr, ", ");
  326.  
  327.     if (RRtotal == 1)
  328.     fprintf(stderr, "1 reduce/reduce conflict");
  329.     else if (RRtotal > 1)
  330.     fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  331.  
  332.     fprintf(stderr, ".\n");
  333. }
  334.  
  335.  
  336. int
  337. sole_reduction(stateno)
  338. int stateno;
  339. {
  340.     register int count, ruleno;
  341.     register action *p;
  342.  
  343.     count = 0;
  344.     ruleno = 0; 
  345.     for (p = parser[stateno]; p; p = p->next)
  346.     {
  347.     if (p->action_code == SHIFT && p->suppressed == 0)
  348.         return (0);
  349.     else if (p->action_code == REDUCE && p->suppressed == 0)
  350.     {
  351.         if (ruleno > 0 && p->number != ruleno)
  352.         return (0);
  353.         if (p->symbol != 1)
  354.         ++count;
  355.         ruleno = p->number;
  356.     }
  357.     }
  358.  
  359.     if (count == 0)
  360.     return (0);
  361.     return (ruleno);
  362. }
  363.  
  364.  
  365. defreds()
  366. {
  367.     register int i;
  368.  
  369.     defred = NEW2(nstates, short);
  370.     for (i = 0; i < nstates; i++)
  371.     defred[i] = sole_reduction(i);
  372. }
  373.  
  374. free_action_row(p)
  375. register action *p;
  376. {
  377.   register action *q;
  378.  
  379.   while (p)
  380.     {
  381.       q = p->next;
  382.       FREE(p);
  383.       p = q;
  384.     }
  385. }
  386.  
  387. free_parser()
  388. {
  389.   register int i;
  390.  
  391.   for (i = 0; i < nstates; i++)
  392.     free_action_row(parser[i]);
  393.  
  394.   FREE(parser);
  395. }
  396.